Матч 22, Последовательность Фибоначчи (FibonacciSequence)

Последовательность чисел Фибоначчи задается следующим рекуррентным соотношением:

F₁ = F₂ = 1,

F_n = F_n-1 + F_n-2

По заданным a и b определить количество чисел Фибоначчи в промежутке от a до b включительно.

Класс: FibonacciSequence

Метод: int numFibs(int a, int b)

Ограничения: 2 £ a £ 1000, a £ b £ 1000.

Вход. Два целых числа a и b.

Выход. Количество чисел Фибоначчи в промежутке от a до b включительно.

Пример входа

a	b
2	5
12	13
13	13

Пример выхода

3

1

1

РЕШЕНИЕ

числа Фибоначчи

Вычислим в массиве m все значения чисел Фибоначчи от m[0] = F₀ = 0 до m[45] = F₄₅ > 1000, используя приведенное выше рекуррентное соотношение. Проходим по массиву m и подсчитываем в переменной c количество чисел Фибоначчи, находящихся в промежутке [a; b].

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

int m[46];

class FibonacciSequence

{

public:

int numFibs(int a, int b)

{

int i, c;

m[0] = 0; m[1] = 1;

for(i = 2; i < 46; i++) m[i] = m[i-1] + m[i-2];

for(c = i = 0; i < 46;i++)

if ((m[i] >= a) && (m[i] <= b)) c++;

return c;

}

};